Simulation of quantum computations on classical computers is desirable. However, such simulations are known to be inefficient processes in terms of both storage space required and time required to perform the simulated computations (execution time).
A quantum computation may be viewed as a serial application of repeated matrix-vector multiplies of an operator (or gate) (u) and a state column vector (or ket) (|Ψ) to thereby generate a new state column vector. This may be expressed as: |Ψnew=Un×Un−1× . . . ×U1|Ψold. A difficulty in simulating such a computation is that for each qubit, the state vector and the operator double in size. A qubit may be defined as a unit of quantum computation, and may be viewed as the functional equivalent of a “bit” in classical computation. In a quantum system with 30 qubits, for example, the state vector has one billion entries and each operator is one billion by one billion in size (230×230). This quickly becomes a problem in both storage size and the amount of time it takes to perform an operation.
Known approaches to improving efficiency in classical simulation of quantum computations have focused on brute force solutions. It would be desirable to employ algorithmic optimizations to increase efficiencies in both dimensions by multiple orders of magnitude, thereby allowing simulations of large quantum systems on classical computer hardware that have not been possible previously.